//
// Created by francklinson on 2021/6/22.
//

//输入一个字符串，打印出该字符串中字符的所有排列。
//你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
private:
    int maxLen = 0;
    vector<string> ans;
    vector<bool> visited;
public:
    vector<string> permutation(string s) {
        maxLen = (int) s.size();
        sort(s.begin(), s.end());
        visited.resize(maxLen);
        string begin;
        backtrack(s, 0, begin);
        return ans;
    }

    /**
     * 递归函数
     * @param s 传入的字符串
     * @param index 搜索到第几位
     * @param curStr 当前得到的字符串
     */
    void backtrack(const string &s, int index, string &curStr) {
        if (index == maxLen) {
            ans.push_back(curStr); // 长度足够了  放入结果数组
            return;
        }
        for (int i = 0; i < maxLen; ++i) {
            // 如果这一位访问过，或者和前一位相同  保限制每次填入的字符一定是这个字符所在重复字符集合中「从左往右第一个未被填入的字符」
            if (visited[i] or (i > 0 and !visited[i - 1] and s[i - 1] == s[i])) continue;
            // 标记
            visited[i] = true;
            curStr.push_back(s[i]);
            // 递归
            backtrack(s, index + 1, curStr);
            // 回溯
            curStr.pop_back();
            visited[i] = false;
        }
    }
};

class Solution2 {
public:
    bool nextPermutation(string &s) {
        int i = s.size() - 2;
        while (i >= 0 && s[i] >= s[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = s.size() - 1;
        while (j >= 0 && s[i] >= s[j]) {
            j--;
        }
        swap(s[i], s[j]);
        reverse(s.begin() + i + 1, s.end());
        return true;
    }

    vector<string> permutation(string s) {
        vector<string> ret;
        sort(s.begin(), s.end());
//        do {
//            ret.push_back(s);
//        } while (nextPermutation(s));
        do {
            ret.push_back(s);
        } while (next_permutation(s.begin(), s.end())); // stl函数 下一个排列

        return ret;
    }

};

int main() {
    Solution2 sol;
    auto ans = sol.permutation("bcac");
    for (auto &x:ans) cout << x << endl;
    return 0;
}